package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid/description/
 * @create 2025/8/31 15:41
 * @since JDK17
 */

public class Solution35 {
    int n, m, ans;
    int[][] dp, g;

    int dfs(int x, int y) {
        if (dp[x][y] != -1) {
            return dp[x][y];
        }
        int p1 = 0, p2 = 0, p3 = 0;
        if (y + 1 < m) {
            if (g[x][y] < g[x][y + 1]) {
                p1 = 1 + dfs(x, y + 1);
            }
            if (x - 1 >= 0 && g[x][y] < g[x - 1][y + 1]) {
                p2 = 1 + dfs(x - 1, y + 1);
            }
            if (x + 1 < n && g[x][y] < g[x + 1][y + 1]) {
                p3 = 1 + dfs(x + 1, y + 1);
            }
        }
        return dp[x][y] = Math.max(Math.max(p1, p2), p3);
    }

    public int maxMoves(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        dp = new int[n][m];
        g = grid;
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        for (int j = 0; j < n; j++) {
            ans = Math.max(ans, dfs(j, 0));
        }
        return ans;
    }
}
